Authenticated data structures provide cryptographic proofs that their answersare as accurate as the author intended, even if the data structure is beingcontrolled by a remote untrusted host. We present efficient techniques forauthenticating data structures that represent graphs and collections ofgeometric objects. We introduce the path hash accumulator, a new primitivebased on cryptographic hashing for efficiently authenticating variousproperties of structured data represented as paths, including any decomposablequery over sequences of elements. We show how to employ our primitive toauthenticate queries about properties of paths in graphs and search queries onmulti-catalogs. This allows the design of new, efficient authenticated datastructures for fundamental problems on networks, such as path and connectivityqueries over graphs, and complex queries on two-dimensional geometric objects,such as intersection and containment queries.
展开▼
